﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 图形数独
{
    public class Calc
    {
        private int n;//是n*n的
        private int[,] mp;//二维数组-1表示空的 1~n 表示填入的数据
        private int[,] result; //最终结果
        public int[,] getMap()
        {
            return mp;
        }

        /// <summary>
        /// 构造方法传入参数
        /// </summary>
        /// <param name="mp"></param>
        /// <param name="n"></param>
        public Calc(int[,] mp, int n)
        {
            this.mp = mp;
            this.n = n;
            this.result = mp;
        }


        /// <summary>
        /// 判断某行某列能否放num这个数
        /// </summary>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <param name="num"></param>
        /// <returns></returns>
        private bool solve(int row, int col, int num)
        {
            //用于记录row col这个点所在的行列所有出现的数字
            List<int> list = new List<int>();
            for (int i = 0; i < 4; ++i)
            {
                if (mp[row, i] != -1)
                {
                    //不存在就放入
                    if (!list.Contains(mp[row, i]))
                    {
                        list.Add(mp[row, i]);
                    }
                }
                if (mp[i, col] != -1)
                {
                    //不存在就放入
                    if (!list.Contains(mp[i, col]))
                    {
                        list.Add(mp[i, col]);
                    }
                }
            }
            //如果这个数已经出现过，就不能放入
            if (list.Contains(num))
            {
                return false;
            }
            //没有出现过，就可以放num这个数
            return true;
        }

        /// <summary>
        /// 深度优先递归放入数据
        /// </summary>
        /// <param name="cal"></param>
        /// <param name="pel"></param>
        public void dfs(int row, int col)
        {
            //递归结束条件，每次列加一，如果列越界，行加一，列清零
            //如果行越界了，就表示所有的数都填完了，结束遍历，将结果map赋值给result
            if (row == n && col == 0)
            {
                //将结果map赋值给result
                setResult();
                return;
            }
            //下一个点的行列
            int nextRow = row;
            int nextCol = col;
            //判断列是否为最后一个，如果是就变成下一行的第一个
            if (col == (n - 1))
            {
                nextRow++;
                nextCol = 0;
            }
            //否则列+1
            else
            {
                nextCol++;
            }
            //如果当前点已经填了值,填充下一个点
            if (mp[row, col] != -1)
            {
                dfs(nextRow, nextCol);
                return;
            }
            //如果当前点没有值，就依次判断是否可以填入1~n
            for (int i = 1; i <= n; i++)
            {
                //判断row col这个点能否放入i这个数
                if (solve(row, col, i))
                {
                    mp[row, col] = i;
                    //能放入就给下个点放入数据
                    dfs(nextRow, nextCol);
                }
            }
            //如果1~n都不能填，就置为-1，让上一个点继续填入下个数
            mp[row, col] = -1;
        }


        /// <summary>
        /// 将结果map赋值给result
        /// </summary>
        private void setResult()
        {
            result = new int[n, n];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    result[i, j] = mp[i, j];
                }
            }
        }

        /// <summary>
        /// 返回最终结果
        /// </summary>
        /// <returns></returns>
        public int[,] getResult()
        {
            dfs(0, 0);
            return result;
        }
    }
}
